Wireless mesh networks have been widely recognized as an emerging technology for low-cost, fast deployment communication networks. Nowadays, they are used in numerous applications, such as wireless backhaul, public safety, and public Internet access. In these applications some wireless routers, referred to as nodes, are statically (i.e., fixed) deployed at different locations. Each node is typically equipped with multiple mesh radios to form a connected mesh. Besides the mesh radios, each node may also have other wireless interfaces that are used to form wireless local area networks (WLANs) for client access. Some of the wireless routers, termed gateways, are connected to the Internet through additional network interfaces. Thus, wireless mesh networks can be used for both local communication and Internet access.
To improve network performance, several equipment vendors connect mesh radios to directional antennas, referred to as directional mesh radios. Directional antennas have a number of technical advantages over conventional omni-directional antennas, including extended transmission range, low interference, low transmission power, and so on, which make them very attractive for static and quasi-static (i.e., limited movement) environments. To simplify network deployment, some vendors utilize a point-to-point paradigm. In particular, each directional mesh radio is paired with another directional mesh radio installed on another node within reach (i.e., neighbors are paired) to form a point-to-point connection between them. To form the connection the two directional mesh radios must be properly oriented toward each other and assigned to the same wireless channel. Directional mesh radios on different links are assigned to orthogonal channels to avoid interference.
Recently, wireless mesh technologies have been used for fast deployment of disaster recovery networks and for military applications. In these applications, wireless mesh routers are mounted on top of moving vehicles or ships. Nodes within such networks/applications are required to identify their neighbors and establish point-to-point connections with some of them to form a robust, connected network regardless of the location of the node(s). We refer to these networks as nomadic wireless mesh networks (NWMN). Unlike ad-hoc networks that provide limited communication capabilities between dynamically moving nodes, NWMNs are required to provide broadband and reliable communications using wireless mesh routers with quasi-static mobility patterns, i.e., a node may change its location but it tends to stay in the same place for a long duration. For such applications, directional mesh radios can be efficiently utilized to establish high capacity point-to-point connections, without suffering from the typical problems of dynamic directional antenna-based environments, such as deafness and hidden nodes.
In some environments/applications (e.g., military) it is important that NWMNs be able to withstand the failure of a link or node. Said another way, it is desirable to provide for dynamic, fault resilient wireless mesh networks. More specifically, it is desirable to provide a robust wireless backbone made up of nodes consisting of wireless mesh routers that (i.e., referred to as “two-edge-connected or two-node-connected” by those skilled in the art) are connected using point-to-point connections between adjacent routers/nodes. In such a resilient network, even if a link or node becomes temporarily unavailable the entire network must remain connected.
Providing robust and resilient NWMNs has its own set of challenges, including determining the types of topologies (e.g., number of nodes, number of directional antennas per node) that assure an NWMN remains operational after suffering a node or link failure.
As is known in the art, determining the topology of a network is a very complex problem. More specifically, such problems are characterized as being “NP-hard” meaning their solutions cannot be found within a reasonable amount of time (i.e., it may take an infinite amount of time to solve them). To determine those topologies of a multi-node wireless mesh network that will remain operational even after a link or node failure, we may turn to mathematics for some guidance. In mathematical terms, a similar problem to the one we face is finding minimum degree spanning subgraphs, i.e. trees or two-connected subgraphs, which is known to be NP-hard for general graphs. Though some have found solutions to this NP-hard problem, none of the solutions can be satisfactorily used to construct robust and resilient NWMNs.
Most researchers that have come before the present inventors have solved so-called “minimum degree spanning subgraph problems” which seek to minimize the degree of a given graph. In contrast, in order to satisfactorily apply the results from a mathematical analysis to our goal of providing robust and resilient NWMNs, solutions to so-called “two-connected subgraphs with bounded node degree problems” must be found. In providing solutions to these problems, the topology of a full graph is not the focus as it is in the minimum degree type problems.
Because a node in a NWMN may only establish point-to-point connections with nodes in its transmission range, a topology model may be modeled by using a so-called “unit disk graph” (UDG).
In brief, a UDG has the following attributes and characteristics. Assuming the use of identical mesh nodes with the same transmission range in all directions, a candidate link exists between two nodes in a full graph if and only if they are within a given distance R from each other. This is a commonly used model for wireless networks and, especially, it is a reasonable model for naval applications, which is one of the applications of NWMNs. In these cases, there are no obstacles between nodes. Two nodes can communicate if their distance does not exceed their transmission range R. In the inventions described below, only high capacity point-to-point connections are used. Thus, we assume that R is selected accordingly.
In terms of UDG graphs, it is highly desirable to provide techniques for calculating bounded degree subgraphs that can, thereafter, be used to construct robust and resilient NWMNs. Said another way, currently, the number of directional antennas and associated mesh radios (collectively referred to as “antenna” or “antennas” because there is usually a one-to-one correspondence between radios and antennas, i.e., one antenna per radio) installed on each node in an NWMN is chosen in a somewhat arbitrary manner. Therefore, it is highly desirable to provide for methods that enable network operators and the like to more definitively determine the number of antennas needed per node.